Introduction

• In ordinary arithmetic, a perfect square is any number of the form $x^2$ for an integer $x$.
  Examples: $0,1,4,9,16,25,\dots$
• In modular arithmetic, we ask a similar but more subtle question:
  Which numbers behave like perfect squares once we reduce everything modulo $n$?
• A number $a$ is called a quadratic residue modulo $n$ if there exists an integer $x$ such that $$x^2 \equiv a \pmod{n}.$$
• If no such $x$ exists, then $a$ is a quadratic non‑residue.
• For example, $6$ is a square mod $10$ (since $4^2 \equiv 6$), but $3$ is not

Why this matters

• Squaring is easy; “unsquaring” (finding square roots) is often hard.
• Patterns of quadratic residues reveal deep structure in modular arithmetic.
• These ideas appear in:
  • primality testing
  • cryptography
  • pseudorandom number generation
  • classical number theory

Perfect Squares in the Integers

• A quick warm‑up:
  • Squares grow quickly: $0,1,4,9,16,25,\dots$
  • Differences between squares: $1,3,5,7,\dots$ (always odd)
• Useful facts:
  • Squares are never negative.
  • Squares mod $n$ “wrap around,” so many more numbers can appear as residues.

Squares Modulo $n$: First Examples

Modulo $7$

Compute $x^2 \bmod 7$ for $x=0$ to $6$:

• $0^2 \equiv 0$
• $1^2 \equiv 1$
• $2^2 \equiv 4$
• $3^2 \equiv 2$
• $4^2 \equiv 2$
• $5^2 \equiv 4$
• $6^2 \equiv 1$

Quadratic residues mod $7$: $\{0,1,2,4\}$

Modulo $10$

• $0^2 \equiv 0$
• $1^2 \equiv 1$
• $2^2 \equiv 4$
• $3^2 \equiv 9$
• $4^2 \equiv 6$
• $5^2 \equiv 5$
• $6^2 \equiv 6$
• $7^2 \equiv 9$
• $8^2 \equiv 4$
• $9^2 \equiv 1$

Quadratic residues mod $10$: $\{0,1,4,5,6,9\}$

Defining Quadratic Residues and Non‑Residues

• A number $a$ is a quadratic residue mod $n$ if $$x^2 \equiv a \pmod{n}$$ has a solution.
• If no such $x$ exists, $a$ is a quadratic non‑residue.
• Examples:
  • $2$ is a residue mod $7$ (since $3^2 \equiv 2$).
  • $3$ is a non‑residue mod $7$.

Patterns of Squares Modulo a Prime

When $p$ is prime:

• There are exactly $\frac{p-1}{2}$ nonzero quadratic residues.
• Squaring “folds” the multiplicative group in half.
• Example mod $11$:
  • Squares: $1,3,4,5,9$
  • Non‑residues: $2,6,7,8,10$

Patterns:

• Residues come in pairs: $$x^2 \equiv (-x)^2 \pmod{p}$$
• Roughly half the numbers are residues, half are not.

Why Some Numbers Are Never Squares Modulo $n$

Reasons include:

• Parity issues:
  • Mod $8$, every odd square is $\equiv 1 \pmod{8}$.
• Prime factorization:
  • If $n$ has prime factors, a number must be a residue modulo each prime power.
• Group structure:
  • In $(\mathbb{Z}/p\mathbb{Z})^\times$, squaring is a 2‑to‑1 map.

Example:

• Mod $8$, the only odd quadratic residue is $1$.

The Structure of the Multiplicative Group Mod $p$

For prime $p$:

• The nonzero numbers mod $p$ form a group under multiplication.
• This group is cyclic:
  • There exists a generator $g$ such that every nonzero number is $g^k$.
• Squares correspond to even exponents: $$g^{2k}$$
• This explains why exactly half the nonzero elements are squares.

The Legendre Symbol: A Compact Notation

The Legendre symbol is a shorthand for “is $a$ a square mod $p$?”: $$\left( \frac{a}{p} \right) = \begin{cases} \;\;1 & \text{if $a$ is a quadratic residue mod $p$ and } a\not\equiv 0 \\ -1 & \text{if $a$ is a non‑residue mod $p$} \\ \;\;0 & \text{if } p \mid a \end{cases}$$ Examples:

• $\left(\frac{2}{7}\right)=1$
• $\left(\frac{3}{7}\right)=-1$
• $\left(\frac{14}{7}\right)=0$

Basic Properties of the Legendre Symbol

Useful rules:

• Multiplicativity: $$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$$
• Squares are always residues: $$\left(\frac{x^2}{p}\right)=1$$
• Reduction:
  • Only the value of $a \bmod p$ matters.

These rules make computations much easier.

Euler’s Criterion

A powerful test for residues: $$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$$

• Only works for prime $p$

Interpretation:

• If $a^{(p-1)/2} \equiv 1$, then $a$ is a residue.
• If $a^{(p-1)/2} \equiv -1$, then $a$ is a non‑residue.

Example mod $11$:

• $2^{5} = 32 \equiv -1 \pmod{11}$
  So $2$ is a non‑residue.

Quadratic Reciprocity: A First Glimpse

One of the most beautiful results in number theory:

For odd primes $p$ and $q$: $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)= (-1)^{\frac{(p-1)(q-1)}{4}}$$ Meaning:

• If both primes are $\equiv 1 \pmod{4}$, residues “match.”
• If both are $\equiv 3 \pmod{4}$, residues “flip.”

Solving Quadratic Congruences

Goal: solve $$x^2 \equiv a \pmod{p}$$ Basic strategies:

• Trial and error for small $p$.
• Use Legendre symbol to check if solutions exist.
• Use structure of the group:
  • If $a = g^k$ and $x = g^m$, then $$2m \equiv k \pmod{p-1}$$
• Tonelli–Shanks algorithm (optional for advanced readers).

Example:

• Solve $x^2 \equiv 4 \pmod{11}$
  • $x \equiv \pm 2 \pmod{11}$

Applications in Cryptography and Pseudorandomness

Quadratic residues appear in:

• Quadratic residue generators (pseudorandom number generators)
• Goldwasser–Micali encryption
• Zero‑knowledge proofs
• Hash functions based on modular squaring

Key idea:

• It is easy to compute $x^2 \bmod n$
• It is often hard to determine whether a number is a square mod $n$ when $n$ is composite.

Common Pitfalls and Misconceptions

• “Half the numbers are residues mod any $n$.”
  • False: only true for primes.
• “If $a$ is a residue mod $p$, then it’s a residue mod $p^k$.”
  • Not always.
• “Residues behave randomly.”
  • They follow deep algebraic patterns.

Summary

• Quadratic residues generalize the idea of perfect squares to modular arithmetic.
• Modulo a prime:
  • Exactly half the nonzero numbers are residues.
  • The Legendre symbol provides a compact notation.
  • Euler’s criterion gives a fast test.
• Quadratic reciprocity links residues across different primes.
• These ideas have real applications in modern cryptography.

Calculator

Exercises

Try to solve these without a calculator when possible.

1. Compute all quadratic residues modulo $9$.

   Solution

   Compute all quadratic residues modulo $9$.

   Compute $x^2 \bmod 9$ for $x = 0,1,\dots,8$:

   • $0^2 \equiv 0$
   • $1^2 \equiv 1$
   • $2^2 \equiv 4$
   • $3^2 \equiv 0$
   • $4^2 \equiv 7$
   • $5^2 \equiv 7$
   • $6^2 \equiv 0$
   • $7^2 \equiv 4$
   • $8^2 \equiv 1$

   Distinct residues:
   $\{0,1,4,7\}$.

2. Determine whether $5$ is a quadratic residue modulo $11$.

   Solution

   Determine whether $5$ is a quadratic residue modulo $11$.

   Compute $x^2 \bmod 11$ for $x = 0,1,\dots,10$:

   • $0^2 \equiv 0$
   • $1^2 \equiv 1$
   • $2^2 \equiv 4$
   • $3^2 \equiv 9$
   • $4^2 \equiv 5$
   • $5^2 \equiv 3$
   • $6^2 \equiv 3$
   • $7^2 \equiv 5$
   • $8^2 \equiv 9$
   • $9^2 \equiv 4$
   • $10^2 \equiv 1$

   We see $4^2 \equiv 5 \pmod{11}$, so $5$ is a quadratic residue modulo $11$.

3. Find all solutions to $x^2 \equiv 6 \pmod{10}$.

   Solution

   Find all solutions to $x^2 \equiv 6 \pmod{10}$.

   Compute $x^2 \bmod 10$ for $x = 0,1,\dots,9$:

   • $0^2 \equiv 0$
   • $1^2 \equiv 1$
   • $2^2 \equiv 4$
   • $3^2 \equiv 9$
   • $4^2 \equiv 6$
   • $5^2 \equiv 5$
   • $6^2 \equiv 6$
   • $7^2 \equiv 9$
   • $8^2 \equiv 4$
   • $9^2 \equiv 1$

   We get $x^2 \equiv 6 \pmod{10}$ for $x \equiv 4,6 \pmod{10}$.

   So the solutions modulo $10$ are $x \equiv 4,6$.

4. Compute $\left(\frac{3}{7}\right)$ using Euler’s criterion.

   Solution

   Compute $\left(\frac{3}{7}\right)$ using Euler’s criterion.

   Euler’s criterion says: $$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}.$$ Here $a=3$, $p=7$, so: $$3^{\frac{7-1}{2}} = 3^3 = 27.$$ Reduce modulo $7$: $$27 \equiv 27 - 21 = 6 \equiv -1 \pmod{7}.$$ So $$\left(\frac{3}{7}\right) = -1,$$ meaning $3$ is a quadratic non‑residue modulo $7$.

5. List all quadratic residues modulo $13$.

   Solution

   List all quadratic residues modulo $13$.

   Compute $x^2 \bmod 13$ for $x = 0,1,\dots,12$:

   • $0^2 \equiv 0$
   • $1^2 \equiv 1$
   • $2^2 \equiv 4$
   • $3^2 \equiv 9$
   • $4^2 \equiv 16 \equiv 3$
   • $5^2 \equiv 25 \equiv 12$
   • $6^2 \equiv 36 \equiv 10$
   • $7^2 \equiv 49 \equiv 10$
   • $8^2 \equiv 64 \equiv 12$
   • $9^2 \equiv 81 \equiv 3$
   • $10^2 \equiv 100 \equiv 9$
   • $11^2 \equiv 121 \equiv 4$
   • $12^2 \equiv 144 \equiv 1$

   Distinct residues:
   $\{0,1,3,4,9,10,12\}$.

   (There are $1 + \frac{13-1}{2} = 7$ residues including $0$, as expected.)

6. Show that every odd square is $\equiv 1 \pmod{8}$.

   Solution

   Show that every odd square is $\equiv 1 \pmod{8}$.

   Let an odd integer be $n = 2k+1$.

   Compute: $$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1.$$ Now $k$ and $k+1$ are consecutive integers, so one of them is even.
   Thus $k(k+1)$ is even, say $k(k+1) = 2m$.

   Then: $$n^2 = 4 \cdot 2m + 1 = 8m + 1 \equiv 1 \pmod{8}.$$ So every odd square is congruent to $1$ modulo $8$.

7. Solve $x^2 \equiv 4 \pmod{17}$.

   Solution

   Solve $x^2 \equiv 4 \pmod{17}$.

   We want all $x$ such that $x^2 \equiv 4 \pmod{17}$.

   Notice:

   • $2^2 = 4 \equiv 4 \pmod{17}$, so $x \equiv 2$ is a solution.
   • Also $(-2)^2 = 4$, and $-2 \equiv 15 \pmod{17}$, so $x \equiv 15$ is another solution.

   Check there are no others: in a prime modulus, a nonzero square has at most two square roots.

   So the solutions are: $$x \equiv 2,15 \pmod{17}.$$

8. Determine whether $10$ is a quadratic residue modulo $19$.

   Solution

   Determine whether $10$ is a quadratic residue modulo $19$.

   Use Euler’s criterion with $a=10$, $p=19$: $$\left(\frac{10}{19}\right) \equiv 10^{\frac{19-1}{2}} = 10^9 \pmod{19}.$$ Compute step by step modulo $19$:

   • $10^2 = 100 \equiv 100 - 95 = 5 \pmod{19}$.
   • $10^4 \equiv 5^2 = 25 \equiv 6 \pmod{19}$.
   • $10^8 \equiv 6^2 = 36 \equiv 36 - 19 = 17 \pmod{19}$.
   • $10^9 \equiv 10^8 \cdot 10 \equiv 17 \cdot 10 = 170 \equiv 170 - 152 = 18 \equiv -1 \pmod{19}$.

   So: $$10^9 \equiv -1 \pmod{19},$$ hence $$\left(\frac{10}{19}\right) = -1.$$ Therefore, $10$ is a quadratic non‑residue modulo $19$.

9. Prove or disprove: “If $a$ is a quadratic residue mod $p$, then $-a$ is also a residue mod $p$.”

   Solution

   Prove or disprove: “If $a$ is a quadratic residue mod $p$, then $-a$ is also a residue mod $p$.”

   Here $p$ is an odd prime.

   • Suppose $a$ is a quadratic residue mod $p$, so $a \equiv x^2 \pmod{p}$ for some $x$.
   • Then $-a \equiv -x^2 \pmod{p}$.

   Question: is $-x^2$ always a square?

   This depends on whether $-1$ is a quadratic residue mod $p$.

   • If $-1$ is a residue, say $-1 \equiv y^2 \pmod{p}$, then $$-a \equiv -x^2 \equiv y^2 x^2 = (xy)^2 \pmod{p},$$ so $-a$ is also a residue.
   • If $-1$ is a non‑residue, then multiplying by $-1$ flips residue/non‑residue status, so $-a$ is a non‑residue.

   Fact: $-1$ is a quadratic residue mod $p$ iff $p \equiv 1 \pmod{4}$.

   So the statement is:

   • True for primes $p \equiv 1 \pmod{4}$.
   • False for primes $p \equiv 3 \pmod{4}$.

   A counterexample:
   Take $p=7$ (which is $3 \pmod{4}$).
   We saw earlier that $2$ is a residue mod $7$ ($3^2 \equiv 2$), but $-2 \equiv 5 \pmod{7}$ is a non‑residue.
   So the statement is not always true.

10. Challenge: Use quadratic reciprocity to determine whether $7$ is a quadratic residue modulo $23$.

    Solution

    Challenge: Use quadratic reciprocity to determine whether $7$ is a quadratic residue modulo $23$.

    We want $\left(\frac{7}{23}\right)$.

    Quadratic reciprocity (for odd primes $p,q$) says: $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}.$$ Here $p=7$, $q=23$.

    Compute the exponent: $$\frac{(7-1)(23-1)}{4} = \frac{6 \cdot 22}{4} = \frac{132}{4} = 33,$$ which is odd, so $$(-1)^{33} = -1.$$ Thus: $$\left(\frac{7}{23}\right)\left(\frac{23}{7}\right) = -1.$$ Now reduce $23$ modulo $7$: $$23 \equiv 2 \pmod{7},$$ so $$\left(\frac{23}{7}\right) = \left(\frac{2}{7}\right).$$ We already know (or can compute) that $2$ is a quadratic residue modulo $7$:

    • $3^2 = 9 \equiv 2 \pmod{7}$, so $\left(\frac{2}{7}\right) = 1$.

    Therefore: $$\left(\frac{7}{23}\right) \cdot 1 = -1 \quad\Rightarrow\quad \left(\frac{7}{23}\right) = -1.$$ So $7$ is a quadratic non‑residue modulo $23$.